[Day10] 30 天挑戰演算法 - 兩個 LinkedList 之和 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

DAY 10

連續30天，挑戰演算法系列第 10 篇

[Day10] 30 天挑戰演算法 - 兩個 LinkedList 之和

鐵人賽

pajace2001

2014-10-10 13:12:42

19773 瀏覽

分享至

題目來源：Add Two Number

問題：
給予兩個 linked lists, 並且在 linked list 裡的所有元素都是正數（沒有負數)而且都是個位數，請試著將兩個 linked list 中的數字個別相加到另一個 linked list，若相加超過各位數則進位下至一個節點。

ListNode 定義

public class ListNode {
    public int val {get; set;}
  public ListNode next {get; set;}
  
  public ListNode(int value){
      this.val = value
    next = null;
  }
}

例子
輸入：linked list1: 2 -> 4 -> 3 ; linked list2: 5-> 6-> 4
輸出：7 -> 0-> 8
因為第二個節點 4 + 6 剛好等於 10，所以進位到下一個節點。因此在處理下一個節點時就會多一個進位過來的數字
3 (linked list 1)+ 4(linked list 2) + 1( 第二節點的進位)

想法
兩個 linked list 的節點相加、進位，乍看之下好像很容易，但第一次做起來卻又一堆問題！
我覺得那因為題目沒說兩個 linked list 的節點數目是否相同，所以這兩種可能都必需要考慮進去。否則就會過不了 test case。
因此，我覺的關於這一題的重點應該是計算兩 linked list相加的中止條件。

那麼中止條件是什麼呢？那就要想題目要求什麼？題目給的限制是：

兩個 linke list 相加
相加後的值只能是個位數，進位要進到下一個節點

所以兩兩相對應節點相加有值產生可能會遇到情況有

兩個節點都不為 null
一個節點是 null
兩個節點都是 null 但上一個節點相加時有進位 (進位的值)

那不可能會有值得情況應該是：

兩個節點都是 null 並且上一節點相加沒有任何進位

所以根據上面的判斷，我們的中止條件應該是：
Linked list1 的節點或 Linked list 2 的節點或進位的值皆為 null
換句話說 [ (Linked list1 Node != null) 或 (LinkedList 2 Node != null) 或 (進位值 != 0 ) ]
因此，找到中止條件之後，整個題目就會變得很簡單了，接下來所要的事情就是兩兩相加了！！

虛擬碼

當 ( **節點1 不等於 null** 或 **節點 2 不等於 null** 或 **進位值 不等於 0**)
    節點1+節點2+進位值 assign 給 sum
    從 sum 取得各位數和十位數
    在回傳的 linked list 上新增一節點並且給值為剛取得的 **個位數**
    將剛取得的十位數暫存在 **進位值** 上
    取得節點1的下一個節點 並 assign 給節點1
    取得節點2的下一個節點 並 assign 給節點2

如果你用 Java or Python or C++ 可上 [LeetCode Online Judge][Problem] 驗證

還是想不出來嗎？參考我的答案吧！

// C# 版本
public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
ListNode dummy = new ListNode(0);
ListNode node = dummy;

 int digitInTens = 0;

 while (list1Node != null || list2Node != null || digitInTens != 0)
 {
     int sum = 0;
     if (list1Node != null && list2Node != null)
         sum = list1Node.val + list2Node.val + digitInTens;
     else if (list1Node != null)
         sum = list1Node.val + digitInTens;
     else if (list2Node != null)
         sum = list2Node.val + digitInTens;
     else
         sum = digitInTens;

     int digitInOnes = sum % 10;

     digitInTens = sum / 10;

     node.next = new ListNode(digitInOnes);
     node = node.next;

     if (list1Node == null)
         list1Node = null;
     else
         list1Node = list1Node.next;

     if (list2Node == null)
         list2Node = null;
     else
         list2Node = list2Node.next;
 }

 return dummy.next;

}

題外話，雖然寫完了但是程式碼實在太醜了，也很難看得懂，我們來 Refactor 一下吧！
首先呢，先幫程式碼加個註解，以方便抽取我們想要的部份

// 加註解的結果

public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

    int digitInTens = 0;

    while (list1Node != null || list2Node != null || digitInTens != 0)
    {
        // 兩個 Linked list 節點相加
        int sum = 0;
        if (list1Node != null && list2Node != null)
            sum = list1Node.val + list2Node.val + digitInTens;
        else if (list1Node != null)
            sum = list1Node.val + digitInTens;
        else if (list2Node != null)
            sum = list2Node.val + digitInTens;
        else
            sum = digitInTens;
                        
        // 取得個位數
        int digitInOnes = sum % 10;
                    
        // 取得十位數
        digitInTens = sum / 10;
        
        // 將個位數新增到結果的 linked list 上
        node.next = new ListNode(digitInOnes);
        node = node.next;

        // linked list 1 取得下一個節點
        if (list1Node == null)
            list1Node = null;
        else
            list1Node = list1Node.next;

        // linked list 2 取得下一個節點
        if (list2Node == null)
            list2Node = null;
        else
            list2Node = list2Node.next;
    }

    return dummy.next;
}

加註解後，就依照各部份使用 Extract Method 取出來吧，讓我們住要的程式碼能夠在同一個表達層級上。

// extract method 後的結果

public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

    int digitInTens = 0;

    while (list1Node != null || list2Node != null || digitInTens != 0)
    {
        int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;

        int digitInOnes = GetDigitInOnes(sum);
        
        digitInTens = GetDigitInTens(digitInTens, sum);
        
        node = AddSumToResultLinkedListNode(node, digitInOnes);

        list1Node = GetNextNode(list1Node);
        list2Node = GetNextNode(list2Node);
    }

    return dummy.next;
}

private static ListNode GetNextNode(ListNode node)
{
    // 取得下一個節點
    if (node == null)
        node = null;
    else
        node = node.next;
    return node;
}

private static ListNode AddSumToResultLinkedListNode(ListNode node, int digitInOnes)
{
    // 將個位數新增到結果的 linked list 上
    node.next = new ListNode(digitInOnes);
    node = node.next;
    return node;
}

private static int GetDigitInTens(int digitInTens, int sum)
{
    // 取得十位數
    digitInTens = sum / 10;
    return digitInTens;
}

private static int GetDigitInOnes(int sum)
{
    // 取得個位數
    int digitInOnes = sum % 10;
    return digitInOnes;
}

private static int CalculateTwoNodeSum(ListNode list1Node, ListNode list2Node)
{
    // 兩個 Linked list 節點相加
    int sum = 0;
    if (list1Node != null && list2Node != null)
        sum = list1Node.val + list2Node.val;
    else if (list1Node != null)
        sum = list1Node.val;
    else if (list2Node != null)
        sum = list2Node.val;
    else
        sum = 0;

    return sum;
}

有沒有覺的，主要的程式碼變得非常清晰了呢？別忘了在每做一次 Extract Method 後，要跑一下 **Unit Test** 以確保程式沒被改壞掉。如果你有潔癖的話，還可以繼續處理抽出來的程式碼：

// 完成重構的程式碼，真乾淨
public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

    int digitInTens = 0;

    while (list1Node != null || list2Node != null || digitInTens != 0)
    {
        int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;

        int digitInOnes = GetDigitInOnes(sum);
        
        digitInTens = GetDigitInTens(digitInTens, sum);
        
        node = AddSumToResultLinkedListNextNode(node, digitInOnes);
        node = GetNextNode(node);

        list1Node = GetNextNode(list1Node);
        list2Node = GetNextNode(list2Node);
    }

    return dummy.next;
}

private static ListNode GetNextNode(ListNode node)
{
    // 取得下一個節點
    return (node == null) ? null : node.next;
}

private static ListNode AddSumToResultLinkedListNextNode(ListNode node, int digitInOnes)
{
    // 將個位數新增到結果的 linked list 上
    node.next = new ListNode(digitInOnes);
    return node;
}

private static int GetDigitInTens(int digitInTens, int sum)
{
    // 取得十位數
    return  sum / 10;
}

private static int GetDigitInOnes(int sum)
{
    // 取得個位數
    return sum % 10;
}

private static int CalculateTwoNodeSum(ListNode list1Node, ListNode list2Node)
{
    // 兩個 Linked list 節點相加
    int sum = GetListNodeValue(list1Node) + GetListNodeValue(list2Node);
    return sum;
}

private static int GetListNodeValue(ListNode node)
{
    if (node != null)
        return node.val;
    return 0;
}

哈哈！似乎有點太過分了！！不過，有沒有注意到我的 if - else 都快被我抽光光的！我認為好的程式碼品質就是要項這樣，跟文章一樣讀起來很輕鬆、很愉快！但前提是必序要有 **足夠的** test case, 不然這樣抽，可能一不小心就把城市給搞壞了！！

最後再回顧一下，這時候如果再替程式碼加上註解，是不視覺的有點雞肋了呢？

// 有點雞肋的註解
while (list1Node != null || list2Node != null || digitInTens != 0)
{
    // 兩節點值相加並 加上前一節點的進位值
    int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;
    // 取得個位數
    int digitInOnes = GetDigitInOnes(sum);
    // 取得十位數
    digitInTens = GetDigitInTens(digitInTens, sum);
    // 將相加的個位數新增至相加結果的 LinkedList 
    node = AddSumToResultLinkedListNextNode(node, digitInOnes);
    node = GetNextNode(node);
    // 取得兩 linked list 的下一節點
    list1Node = GetNextNode(list1Node);
    list2Node = GetNextNode(list2Node);
}